r"""
Alphabets for words (or really, for anything else)

See the documentation for the Alphabet class inside this module
for details and examples.

AUTHORS:
    -- Arnaud Bergeron
"""
#*****************************************************************************
#       Copyright (C) 2008 Arnaud bergeron <abergeron@gmail.com>
#
#  Distributed under the terms of the GNU General Public License version 2 (GPLv2)
#
#  The full text of the GPLv2 is available at:
#
#                  http://www.gnu.org/licenses/
#*****************************************************************************
from itertools import izip, count, imap
from sage.structure.sage_object import SageObject
from sage.misc.latex import latex
from weakref import WeakValueDictionary
from utils import *

class Alphabet(SageObject):
    r"""
    This class represents an immutable ordered collection of symbols.
    
    It has a set-like interface so you can ask whether it contains a 
    symbol or not.  The comparison operators have the same logic as set.
    
    This class also enforces certain guarantees that are not provided
    by a simple set.  In particular, the order of iteration will always
    match the order of the symbols and the string representation is fixed
    for a given alphabet.
    
    One place where it differs the most from a set is in the equality
    comparison.  It takes into account the order of the symbols and two
    alphabets are not equal if they don't have the same order.
    
    INPUT:
        obj -- an iterable yielding symbols in their comparison order
    
    EXAMPLES:
    
    For a simple alphabet over 'a', 'b' and 'c' you can say:
        sage: a = Alphabet('abc')
        
    If you want integers as symbols then you can't use a string, 
    but a list will do:
        sage: a = Alphabet([1, 2])
        
    You can use almost anything as symbols:
        sage: a = Alphabet((xrange(2), xrange(3)))
        
    And the symbols don't even have to be of the same type:
        sage: a = Alphabet([xrange(42), "foo", False, complex(0, 1)])
    """
    _alpha_cache = WeakValueDictionary()
    
    def __new__(cls, obj):
        r"""
        Builds a new alphabet from an iterable.  
       
        The ordering is assumed to be the order the items appear in 
        the iterable.  There must be no duplicates.
        
        TESTS:
            sage: a = Alphabet("abc")
            sage: Alphabet('aba')
            Traceback (most recent call last):
            ...
            ValueError: duplicate key(s) in alphabet
            sage: Alphabet(33)
            Traceback (most recent call last):
            ...
            TypeError: cannot build an alphabet with 33
            sage: Alphabet('ab') is Alphabet('ab')
            True
            sage: Alphabet('ab') is Alphabet(['a', 'b'])
            True
            sage: Alphabet('abc') is not Alphabet('ab')
            True
            sage: a == loads(dumps(a))
            True
        """
        if isinstance(obj, dict):
            raise NotImplementedError
        try:
            t = tuple(obj)
        except TypeError:
            raise TypeError, "cannot build an alphabet with %s" % (obj)
        if t not in cls._alpha_cache:
            self = super(Alphabet, cls).__new__(cls)
            self._fwd = dict(izip(count(), t))
            self._rev = reverse_map(self._fwd)
            if len(self._rev) != len(self._fwd):
                raise ValueError, "duplicate key(s) in alphabet"
            cls._alpha_cache[t] = self
        return cls._alpha_cache[t]
    
    def __getnewargs__(self):
        r"""
        pickle support
        
        TESTS:
            sage: Alphabet('ab').__getnewargs__()
            (('a', 'b'),)
        """
        return (tuple(self),)
        
    def __getstate__(self):
        r"""
        pickle support
        
        TESTS:
            sage: Alphabet('ab').__getstate__()
        """
        pass
    
    def __setstate__(self):
        r"""
        pickle support
        
        TESTS:
            sage: Alphabet('ab').__getstate__()
        """
        pass
    
    def to_sym(self, index):
        r"""
        Maps the integer to the corresponding symbol.
        
        INPUT:
            index -- an integer between 0 and len(self)
        
        OUTPUT:
            symbol -- the corresponding symbol
            
        EXAMPLES:
            sage: Alphabet('abcd').to_sym(0)
            'a'
            sage: Alphabet('abcd').to_sym(3)
            'd'
            sage: Alphabet('abcd').to_sym(4)
            Traceback (most recent call last):
            ...
            IndexError: index out of alphabet
            sage: Alphabet('abcd').to_sym(-1)
            Traceback (most recent call last):
            ...
            IndexError: index out of alphabet
        """
        if not 0 <= index < len(self):
            raise IndexError, 'index out of alphabet'
        return self._fwd[index]
    
    def to_int(self, symbol):
        r"""
        Maps the symbol to the corresponding integer representation.
        
        INPUT:
            symbol -- a symbol contained in this alphabet
        
        OUTPUT:
            integer -- the integer mapping for the symbol
        
        EXAMPLES:
            sage: Alphabet('abcd').to_int('a')
            0
            sage: Alphabet('abcd').to_int('d')
            3
            sage: Alphabet('abcd').to_int('e')
            Traceback (most recent call last):
            ...
            IndexError: symbol not in alphabet: 'e'
            sage: Alphabet('abcd').to_int('')
            Traceback (most recent call last):
            ...
            IndexError: symbol not in alphabet: ''
        """
        if not symbol in self._rev:
            raise IndexError, "symbol not in alphabet: %s" % repr(symbol)
        return self._rev[symbol]
    
    def min_sym(self):
        r"""
        Returns the smallest symbol in the alphabet.
        
        Smallest is determined by the sorting order provided
        at the creation of the alphabet, not by the natural
        sort of the elements, if any.
        
        This function is undefined on empty alphabets.
        
        OUTPUT:
            symbol -- the smallest symbol
        
        EXAMPLES:
            sage: Alphabet('123').min_sym()
            '1'
            sage: Alphabet('dagebc').min_sym()
            'd'
            sage: Alphabet('').min_sym()
            Traceback (most recent call last):
            ...
            ValueError: undefined value, alphabet is empty
        """
        if len(self._fwd) != 0:
            return self._fwd[0]
        raise ValueError, 'undefined value, alphabet is empty'
    
    def max_sym(self):
        r"""
        Returns the maximal symbol in the alphabet.
        
        Maximal is determined by the sorting order provided
        at the creation of the alphabet, not by the natural
        sort of the elements, if any.
        
        This function is undefined on empty alphabets.
        
        OUTPUT:
            symbol -- the biggest symbol
        
        EXAMPLES:
            sage: Alphabet('123').max_sym()
            '3'
            sage: Alphabet('dagebc').max_sym()
            'c'
            sage: Alphabet('').max_sym()
            Traceback (most recent call last):
            ...
            ValueError: undefined value, alphabet is empty
        """
        if len(self._fwd) != 0:
            return self._fwd[len(self._fwd) - 1]
        raise ValueError, 'undefined value, alphabet is empty'
    
    def __iter__(self):
        r"""
        Iterates over the symbols of the alphabet in order.
        
        EXAMPLES:
            sage: list(Alphabet('312'))     # indirect test
            ['3', '1', '2']
        """
        for i in xrange(len(self._fwd)):
            yield self._fwd[i]
    
    def string_rep(self):
        r"""
        Returns the string representation of the alphabet.
        
        TESTS:
            sage: Alphabet('cba').string_rep()
            "['c', 'b', 'a']"
            sage: Alphabet([1, 3, 2]).string_rep()
            '[1, 3, 2]'
        """
        return "[%s]" % ', '.join(imap(repr, self))
    
    def _repr_(self):
        r"""
        Returns a printeable representation of the alphabet.
        
        TESTS:
            sage: Alphabet('cba')._repr_()
            "Alphabet: ['c', 'b', 'a']"
            sage: Alphabet([1, 3, 2])._repr_()
            'Alphabet: [1, 3, 2]'
        """
        return "Alphabet: %s" % self.string_rep()
    
    def _latex_(self):
        r"""
        Returns a \Latex representation of the alphabet.
        
        TESTS:
            sage: Alphabet('cba')._latex_()
            '[\\text{c}, \\text{b}, \\text{a}]'
            sage: Alphabet([3, 1, 2])._latex_()
            '[3, 1, 2]'
        """
        return "[%s]" % ', '.join(imap(latex, self))
    
    def __len__(self):
        r"""
        Returns the number of symbols in the alphabet.
        
        EXAMPLES:
            sage: len(Alphabet('abc'))
            3
            sage: len(Alphabet(xrange(5)))
            5
        """
        return len(self._rev)
    
    def __le__(self, other):
        r"""
        Returns whether other is a superset of this alphabet or not.
        
        The ordering of the symbols is ignored for this.
        
        EXAMPLES:
            sage: Alphabet('abc') <= Alphabet('daefbgc')
            True
            sage: Alphabet('abc') <= Alphabet('abc')
            True
            sage: Alphabet('abc') <= Alphabet('ac')
            False
            sage: Alphabet('abc') <= Alphabet([1, 2, 3])
            False
        """
        if not isinstance(other, Alphabet):
            return NotImplemented
        for s in self:
            if s not in other:
                return False
        else:
            return True
    
    def __ge__(self, other):
        r"""
        Returns whether other is a subset of this alphabet or not.
        
        The ordering of the symbols is ignored for this.
        
        EXAMPLES:
            sage: Alphabet('abc') >= Alphabet('daefbgc')
            False
            sage: Alphabet('abc') >= Alphabet('abc')
            True
            sage: Alphabet('abc') >= Alphabet('ac')
            True
            sage: Alphabet('abc') >= Alphabet([1, 2, 3])
            False
        """
        if not isinstance(other, Alphabet):
            return NotImplemented
        for s in other:
            if s not in self:
                return False
        else:
            return True
    
    def __contains__(self, symbol):
        """
        Returns true if this alphabet contains the symbol.
        
        INPUT:
            symbol -- an object
            
        OUTPUT:
            boolean -- whether this alphabet contains the symbol or not
        
        EXAMPLES:
            sage: 'a' in Alphabet('ab')
            True
            sage: 'c' in Alphabet('ab')
            False
        
        TESTS:
            sage: ['a', 'b'] in Alphabet('ab')
            False
        """
        try:
            return symbol in self._rev
        except TypeError:
            return False
